package algorithm.leetcode.I1to100;

/**
 * 除法在计算机中的实现
 * 其实挺有意思的
 *
 */

// e.g. 100 / 3 的算法
// 被除数是100, 3 不断的右移动,直到当前仍小于或等于100而下一次右移大于100,记此时右移动的位数为K,显然本例中K等于5,第一次商累计为2^5=32
// 被除数变为100-3>>5 = 4, 3 继续按上面的规律右移,显然此次K等于0,第二次商累计为2^0=1
// 被除数变为1-3>>0 = -2, 当被除数小于0的时候退出循环
// 累计上面所有右移位数的十进制表示之和, 商=32+1=33
//
// trick:
// Java int类型的范围是 -2^32 ~ 2^32-1,负数的个数比正数多一个,故可以全部转化为负数去计算,注意此时不等号的方向


public class Q29 {

    public int divide(int dividend, int divisor) {
        // 处理一些特殊情况
        if (dividend == 0) return 0;
        else if (divisor == 1) return dividend;
        else if (divisor == -1 && dividend == Integer.MIN_VALUE) return Integer.MAX_VALUE;
        else if (divisor == -1) return -dividend;

        // 正常情况,为了防止溢出全部转为负数
        else {
            // 确定一下符号
            int sign = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0) ? 1 : -1;
            dividend = dividend < 0 ? dividend : -dividend;
            divisor = divisor < 0 ? divisor : -divisor;
            return sign < 0 ? -divideHelper(dividend, divisor) : divideHelper(dividend, divisor);
        }
    }

    public static int divideHelper(int a, int b) {
        if (a > b) return 0;

        int aa = 1;
        int bBackup = b;
        // 这个while里的条件是难点,首先要避免bBackup溢出,其次是后面的大于等于号,考虑a=-4,b=-2,这种情况=也是要放进去的
        while (bBackup >= (Integer.MIN_VALUE >> 1) && bBackup + bBackup >= a) {
            bBackup = bBackup + bBackup;
            aa = aa + aa;
        }
        return aa + divideHelper(a-bBackup, b);
    }

    public static void main(String[] args) {
        System.out.println(divideHelper(-2147483648, -2));
        System.out.println(Integer.MIN_VALUE >> 1);
    }

}
